#include <algorithm>
#include <cstring>
#include "reference_calc.h"

void reference_calculation(unsigned int* inputVals,
                         unsigned int* inputPos,
                         unsigned int* outputVals,
                         unsigned int* outputPos,
                         const size_t numElems)
{
  // 定义每次处理的比特位数
  const int numBits = 1;
  // 计算桶的数量(2^numBits)
  const int numBins = 1 << numBits;

  // 分配用于统计每个桶中元素数量的数组
  unsigned int *binHistogram = new unsigned int[numBins];
  // 分配用于记录每个桶起始位置的数组
  unsigned int *binScan      = new unsigned int[numBins];

  // 设置源数据指针(值和位置)
  unsigned int *vals_src = inputVals;
  unsigned int *pos_src  = inputPos;

  // 设置目标数据指针(值和位置)
  unsigned int *vals_dst = outputVals;
  unsigned int *pos_dst  = outputPos;

  // 基数排序主循环，每次处理numBits位
  for (unsigned int i = 0; i < 8 * sizeof(unsigned int); i += numBits) {
    // 创建掩码用于提取当前处理的比特位
    unsigned int mask = (numBins - 1) << i;

    // 清零直方图数组
    memset(binHistogram, 0, sizeof(unsigned int) * numBins);
    // 清零扫描数组
    memset(binScan, 0, sizeof(unsigned int) * numBins);

    // 构建直方图：统计每个桶中的元素数量
    for (unsigned int j = 0; j < numElems; ++j) {
      // 计算当前元素所属的桶
      unsigned int bin = (vals_src[j] & mask) >> i;
      binHistogram[bin]++;
    }

    // 计算exclusive前缀和，确定每个桶的起始位置
    for (unsigned int j = 1; j < numBins; ++j) {
      binScan[j] = binScan[j - 1] + binHistogram[j - 1];
    }

    // 根据前缀和将元素放入正确的位置
    for (unsigned int j = 0; j < numElems; ++j) {
      unsigned int bin = (vals_src[j] & mask) >> i;
      // 将值放入目标数组
      vals_dst[binScan[bin]] = vals_src[j];
      // 将位置信息放入目标数组
      pos_dst[binScan[bin]]  = pos_src[j];
      // 更新桶的起始位置
      binScan[bin]++;
    }

    // 交换源和目标指针，为下一轮排序做准备
    std::swap(vals_dst, vals_src);
    std::swap(pos_dst, pos_src);
  }

  // 由于进行了偶数次迭代，需要将结果从输入缓冲区复制到输出缓冲区
  std::copy(inputVals, inputVals + numElems, outputVals);
  std::copy(inputPos, inputPos + numElems, outputPos);

  // 释放动态分配的内存
  delete[] binHistogram;
  delete[] binScan;
}
